1. Field of the Invention
The present invention relates to generating random numbers and, in particular, to a concept for generating a quantity of statistically independent bits in which the bit values 0 and 1 occur with the same frequency.
2. Description of Prior Art
There are various applications in which random numbers have to be generated. When for example transmitting data in an encrypted manner, the keys may be generated based on random numbers. A reliable generation of random numbers is an indispensable prerequisite for safe data transmission. Implementing a random generator in a chipcard is of interest for mobile applications to enable a safe digital signature, wherein this application has gained in importance in the recent past.
Here, it is of particular importance that the frequency with which the values 0 and 1 are generated is, on average, identical for a random number generator which is to generate a sequence of random bits of the values 0 and 1. If this was not the case, it would be made easy for a potential attacker to compromise the system by utilizing, for his attack, the fact that one of the values 0 or 1 is generated more frequently. Experience has shown that physical random number generators, however, exhibit a certain deviation from the mathematical ideal case of the statistically independent random bits with a 1 and a 0 probability of ½, regardless of their operating principle. A number of random bits, for example, are frequently generated by observing a physically generated noise voltage, wherein the noise voltage is digitalized (sampled) in discrete periods of time and a bit of the value 1 will be output if a reference voltage value is exceeded at the time of sampling, whereas a bit of the value 0 will be output if the result is below the reference voltage. Often, a semiconductor pattern is used for generating the noise voltage. An addition of a constant voltage offset to the noise voltage, as is exemplarily caused by a change in temperature, obviously changes the probability with which the values 0 or 1 are generated. Deviations from the desired ideal behavior of a random number generator result in this way.
If the probability of 1 bits occurring deviates from the ideal value of ½, we talk of skewness of the random bits generated. In order to prevent this, there is a way of intervening in the source by controlling, which, for the above example, would mean adding an additional controlled offset voltage of the noise voltage. If too many ones have resulted, the parameters of the generator will be changed such that more zeros will be formed, and vice versa. Frequently, the difference between the number of 1 bits formed since the start of the generator and the 0 bits formed since the start is used as a measure of the 1 excess. (This may be achieved in an, as far as technology is concerned, easy manner by and up/down counter incrementing its value in the case of 1 bits and decrementing for 0 bits.) Depending on the count, the operating point of the generator is then shifted such that the bit value with a lack of frequency will be generated more frequently.
A problem of the skewness control just described is that statistical dependences result between the bits. Obviously, with this skewness control, the occurrence of many subsequent zeros, for example, will increase the probability of a 1-bit occurring. Here, this dependence is not only present over a few neighboring bits, but in principle over any distances and times. Such a dependence contradicts the principle of an ideal random number generator where it is the very aim to generate any number generated with always the same probability, i.e. independently of the numbers generated in the past. The random numbers generated one after the other thus are to be statistically independent.
Frequently, the deviations from the mathematical ideal case are reduced by algorithmic post-processing of the bits generated by a random bit generator. A precondition for this is that the random bits generated by the generator are statistically independent and that, additionally, the probabilities with which the values 0 or 1 are generated are constant over time, wherein these need not necessarily be exactly ½.
A statistical measure of the information content of a certain piece of information I (such as, for example, a number of random number bits) over an alphabet Z (in the case of random bits, the alphabet consists of the values 0 and 1) is the entropy H defined as follows:
      H    ⁡          (      I      )        =      -                  ∑                  j          =          1                                    z                              ⁢                        pj          ·                      log            2                          ⁢        pj            
Thus, pj is the probability with which the jth symbol (0 or 1) of the alphabet Z occurs in the information text I. Although the calculation of the entropy H may also be transferred to different number systems (such as, for example, octal numbering system, hexadecimal system) than the binary system, only the application of the above definition to the binary system is of importance for the following discussion. The maximum value of the entropy obtainable for a sequence of random numbers is 1, wherein the entropy H will take the value 1 precisely if the number of the values 0 and 1 in the sequence of the random bits generated (the information text) is identical.
A skewness when generating random numbers thus corresponds to an entropy smaller than 1. An increase in entropy by algorithmic post-processing procedures can only be achieved by means of compression, i.e. more than one input bit of a random number generator is required to generate a final output bit. A well-known example of algorithmic post-processing of this kind is the method by John von Neumann, which is described in the publication “Various Techniques Used In Connection With Random Digits”, John von Neumann, Collected Works, Volume V, Pergamon Press, 1963. Here, a sequence of statistically independent output bits having the same probability z1, z2, . . . zm is generated from an input bit sequence x1, x2, . . . xn. It is a precondition here that the input bits of the input bit sequence are statistically independent of one another and that the probability of the input bits xi having the value 0 or 1 is constant over time. This is to say:P(xi=1)=p, and P(xi=0)=q=1−pis true for all n. Von Neumann thus summarizes two each of the input bits xi and uses the following mapping:(1) 00→Λ 01→0, 10 →1, 11→Λ,wherein Λ means that no output bit will be output. If the bit sequence 01 is generated, a 0 will be output by the Von Neumann mapping, if the bit sequence 10 is generated, a 1 will be output, wherein both cases each occur with the same probability pq. Using the above assumptions for the input bits xi, a bit sequence of statistically independent bits is generated by the algorithmic post-processing suggested by Von Neumann, wherein the different bit valencies occur with the same constant probability of ½.
Further procedures based on the principle of increasing the entropy by compression are described in “Iterating Von Neumann's Procedure For Extracting Random Bits” by Yuval Peres, The Annals of Statistics, 1992, Vol. 20, No. 1, 590-597, and in “The Efficient Construction of an Unbiased Random Sequence” by Peter Elias, The Annals of Mathematical Statistics, 1972, Vol. 43, No. 3, 65-870. A widely used form of compression is XOR operating several input bits to form one output bit.
There is also demand for algorithmic post-processing of the bits generated for random number generators where skewness is eliminated by means of control. Here, it may be an aim of such a post-processing to eliminate or reduce the dependences caused by the control, wherein no post-processing functions achieving this aim are known from the prior art. It is generally required for an algorithmic post-processing of a random number source comprising skewness correction by means of control that the entropy must not be reduced by the algorithmic post-processing. At present, there is no proof that the post-processing methods known so far do not reduce entropy, wherein in particular the difficulties are that the dependences occur over any period of time and that the probabilities corresponding to the individual counts are not known.
In general, the problem with a combination of a random number generator based on skewness control and algorithmic post-processing is that statistical dependences between the bits generated are caused by the skewness control, wherein a precondition for applying a post-processing algorithm, however, is statistical independence of the input bits and a temporally constant probability of generating the values 0 and 1. While the requirement for time stability of the generation probability can be met by the control, this control, however, provides an undesired statistical dependence between the bits provided as input bits for the algorithmic post-processing.